package Task33;

import java.util.Scanner;

public class Main2 {
        public static void main(String[] args){
            int border = -1;
            long[] ans = new long[100000];
            ans[0] = 1;
            ans[1] = 2;
            for(int i =2;i< 100000;i++){
                long next = ans[i-1] + ans[i-2];
                if(border == -1 && next >=1000000){
                    border = i+1;
                }
                ans[i] = next % 1000000 ;
            }
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){
                int n = sc.nextInt();
                if(border >= n){
                    System.out.println(ans[n-1]);
                }else{
                    System.out.printf("%06d\n",ans[n-1]);
                }

            }
        }
}